import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-22
 * Time: 19:36
 */

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
class Node{
    public TreeNode treeNode;
    public int index;
    public Node(TreeNode treeNode,int index){
        this.treeNode=treeNode;
        this.index=index;
    }
}
class Solution {
    //bfs
    public int widthOfBinaryTree(TreeNode root) {
        int max=1;
        Queue<Node> queue=new LinkedList<>();
        TreeNode cur=root;
        queue.offer(new Node(cur,1));
        while(!queue.isEmpty()){
            //每进一次这个循环都是新的一层
            int start=queue.peek().index;
            int end=queue.peek().index;
            int size=queue.size();
            for(int i=0;i<size;i++){
                Node temp=queue.poll();
                int index=temp.index;
                end=index;
                if(temp.treeNode.left!=null){
                    queue.offer(new Node(temp.treeNode.left,index*2));
                }
                if(temp.treeNode.right!=null){
                    queue.offer(new Node(temp.treeNode.right,index*2+1));
                }
            }
            int width=end-start+1;
            if(width>max){
                max=width;
            }
        }
        return max;
    }
}
